GATE CSE 2009 | Question: 17

Question

Match all items in Group 1 with the correct options from those given in Group 2.$$\begin{array}{|ll|ll|}\hline \rlap{\textbf{Group 1}} & & \rlap{\textbf{Group 2}}  \\\hline \text{P.} & \text{Regular Expression} & \text{1.} & \text{Syntax analysis} \\\hline  \text{Q.} & \text{Pushdown automata} & \text{2.}& \text{Code generation} \\\hline   \text{R.}& \text{Dataflow analysis} & \text{3.}  & \text{Lexical analysis} \\\hline  \text{S.} & \text{Register allocation} &\text{4.}  & \text{Code optimization}  \\\hline \end{array}$$

• A. $\text{P-4, Q-1, R-2, S-3}$
• B. $\text{P-3, Q-1, R-4, S-2}$
• C. $\text{P-3, Q-4, R-1, S-2}$
• D. $\text{P-2, Q-1, R-4, S-3}$

Comments

@Shaik Masthan sir , how to know this code optimisation is m/c independent code optimization which optimize the Intermediate code , OR it is talking abt m/c dependent optimizer where we do optimization of target code.

And, here sir Register allocation is Target Code generation part .

---

Generally they need to specify in the question itself.

For this question, by matching other options, we would left with only one choice.

Answer 1

Correct Option: B

Regular expressions are used in lexical analysis.

Pushdown automata is related to context free grammar which is related to syntax analysis.

Dataflow analysis is done in code optimization.

Register allocation is done in code generation.

Comments

How come ? Give source... acc. to me   During code generation, we allocate the registers..

---

How data flow analysis actually works in code optimization ?

---

Data Flow Analysis has properties called

1)Available Expression

2)Reaching Definition

These two properties help in code optimization

Answer 2

1.lexer understand codes of a programme and lexer uses pattern to generate token
now pattern are expressed by regular expression ir L(L+D)* for recognizing keywords .
2.we use grammars to define syntax of a programme how lets see
   a + b * c  this is our expression in one c programme
  now related cfg is 
    E → E + T | T
    T → T * F | F
    F → (E) | id
 now with this grammar help we generate syntax tree or called derivation tree
so grammars are well knows for synatx tree 
remember syntax tree are also one form of intermeditate code which is source language depenedent machine code
and obviously we use PDA to accept CFG
 

3.code optimization has basically two parts
  data flow analysis and control flow analysis
data flow analysis does what-its concerned with how  data flows and this analysis helps us to 
subparts of data flow analysis is

Live Variable Analysis
 for register allocation and dead code elimination

Available Expressions Analysis
  common subexpression elimination and copy propogation

Constant Propagation Analysis
note:
Register allocation is also part of optimization i dont know how it helps in code generation

 

Answer 3

Group1	Group2
P. Regular Expression	3. Lexical analysis
Q. Pushdown automata	1. Syntax analysis
R. Dataflow analysis	4. Code optimization
S. Register allocation	2. Code generation

Answer : B